\documentclass{article}

\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsmath,amssymb,amscd,epsfig,amsfonts,rotating}
\usepackage{graphicx}
\usepackage{epsfig}
\usepackage{multirow}
\usepackage{booktabs}
\usepackage{url}

\title{Assginment 2 of Mathematics in Computer Science 2}
\author{Weinan Zhang}
\date{22 May 2012}
\begin{document}
\maketitle


\section*{Ex 2.36 (40 points)}
\textbf{Question.} Randomly generate a 100 points on the surface of a sphere in 3-dimensions and in 100-dimensions. Create a histogram of all distances between the pairs of points in both cases.\\
\textbf{Answer.} Write a matlab program. For each dimension, use Gaussian distribution to generate data. If the data point is out of the sphere, delete it and generated again. If it is inside sphere, directly map it to the surface. Finally, make a statistics on the distances of pairs of data points and result in the histogram below.

\begin{figure}[!ht]
\centering
\includegraphics[width=0.9\textwidth]{mathcs236.pdf}
\caption{Statistics on the distances of data point pairs.}\label{fig:histo}
\end{figure}

In Figure \ref{fig:histo}, the distances are distributed in 30 buckets. Moreover, x-axis label is counted by the bucket index $i$, which corresponds the pairs with distances in $[\frac{i-1}{30}, \frac{i}{30})$.

From the different distribution of distances of these pairs in dimension 3 and 100, we can see that as the dimension number $d$ increases, the distances between two points on the surface of $d$-dimensional sphere trend to have a higher mean and lower variance.

\section*{Ex 2.37 (30 points)}
\textbf{Question.} We have claimed that in high dimensions a unit variance Gaussian centered at the origin has essentially zero probability mass in a unit-radius sphere centered at the origin since the unit-radius sphere has no volume. Explain what happens if the Gaussian has an extremely small variance and has no probability mass outside the unit-radius sphere? How small must the variance be in terms of d for this to happen? \\
\textbf{Answer.} The $d$-dimensional spherial Gaussian with zero mean and variance $\sigma$ has density fuction
\[ p(r) = \frac{1}{(2\pi)^{d/2}\sigma^d} \exp\left( - \frac{r^2}{2\sigma^2}\right). \]
The probability mass of the Gaussian as a function of $r$ is
\[ g(r) = \frac{r^{d-1}}{\sigma^d} exp\left( - \frac{r^2}{2\sigma^2}\right). \]
Let $c$ be a positive real and let $I$ be the interval $[\sigma\sqrt{d-1} - c, \sigma\sqrt{d-1} + c]$. Then we have the mass outside the interval $I$ is upper bounded by
\begin{align*}
\int_{r\notin I}g(r)dr & \leq 2g(\sqrt{d - 1}) \int_{r = \sqrt{d-1}+c}^{\infty} e^{-\frac{1}{2\sigma^2}(r - \sigma\sqrt{d-1})^2} dr\\
 & \leq 2g(\sqrt{d - 1}) \frac{1}{\sigma} \int_{\frac{y = c}{\sigma}}^{\infty} e^{-\frac{y^2}{2}}dy\\
 & \leq 2g(\sqrt{d - 1}) \frac{1}{\sigma} \int_{\frac{y = c}{\sigma}}^{\infty} \frac{y\sigma}{c} e^{-\frac{y^2}{2}}dy\\
 & \leq \frac{8}{c^2} e^{- \frac{c^2}{4\sigma^2}}.\\
\end{align*}
Let $c = 1 - \sigma\sqrt{d - 1}$. We get
\[ \int_{r\notin I}g(r)dr \leq \frac{8}{(1 - \sigma\sqrt{d-1})^2} e^{- \frac{(1 - \sigma\sqrt{d-1})^2}{4\sigma^2}}. \]
We can see that when $\sigma = o(\frac{1}{\sqrt{d}})$, this upper bound will trend to zero as $d$ increases.

\section*{Ex 2.50 (30 points)}
\textbf{Question.} Create a list of the five most important things that you learned about high dimensions.\\
\textbf{Answer.} This is an open question. For me, the five most important thing I learned are as below.
\begin{itemize}
\item The notion of the surface and volume of the sphere and the cube in higher dimensions.
\item The volume of a unit-radius sphere trends to zero with the increasing of dimension. This is not intuitive at the start but now I has a more intuitive comprehension about that: the point $x = (x_1, x_2, \ldots, x_d)$ in the sphere should satisfy
    \[ \sum_{i = 1}^{d}{x_i^2} \leq 1, \]
    where the number of $x_i$ increase while the sum keeps constant 1. Thus it makes this condition more strict as the dimension $d$ increases.
\item The uniform data points generation on the surface of a $d$-dimensional sphere. Here the method of uniform generation on each dimension followed by a dropping off for the point outside the sphere does not work in high dimension because the volume of high dimensional unit-radius sphere trends to zero and it has almost no possibility to generate such in-sphere points. A solution is to replace the uniform generation by a low-variance Gaussian generation.
\item The condition of the distance $\delta$ between two $d$-dimensional Gaussian that requires the distances from the same Gaussian is no larger than the ones from different Gaussian.
    \[ \delta \in \Omega(d^{1/4}) \]
    This condition is usually unsatisfiable in the real world datasets when the dimension $d$ is much high.
\item Random projection and the Johnson-Lindenstrauss Theorem. The random projection from a higher $d$-dimension space to a lower $k$-dimension subspace will to some extent shorten the length of a unit length vector \textbf{$v$} with a rate of $\frac{k}{d}$. Therefore, it results in the latter Johnson-Lindenstrauss Lemma that it has a low probability that any pair has a large distortion from the projection.
\end{itemize}

\end{document}
